package cg.studio.algorithm.search;

import java.util.Comparator;

/**
 * The inputed collection or array should be sorted.
 * @author Bright Chen
 *
 */
public class SearchOnSorted implements Searcher
{
  public <T> boolean hasValue( T[] array, T value, Comparator<T> comparator )
  {
    return hasValueByIndex( array, value, comparator );
  }
  
  public <T> boolean hasValueByLength( T[] array, T value, Comparator<T> comparator )
  {
    if( array ==  null || array.length == 0 )
      return false;
    if( comparator.compare( value, array[0] ) < 0 && comparator.compare( value, array[array.length-1] ) > 0 )
      return false;
    
    //get rid of recursion
    int startIndex = 0;
    int length = array.length;
    while( length >= 1 )
    {
      if( length == 1 )
        return ( comparator.compare( value, array[startIndex] )==0 );
      
      int newLength = length/2;
      int ret = comparator.compare( value, array[ startIndex + newLength ] );
      if( ret == 0 )
        return true;
      if( ret > 0 )
      {
        startIndex += (newLength+1);
        length -= ( newLength+1 );
      }
      else
      {
        length = newLength;
      }
    }
    return false;
  }
  

  //this logic is easier
  public <T> boolean hasValueByIndex( T[] array, T value, Comparator<T> comparator )
  {
    if( array ==  null || array.length == 0 )
      return false;
    if( comparator.compare( value, array[0] ) < 0 && comparator.compare( value, array[array.length-1] ) > 0 )
      return false;
    
    //get rid of recursion
    int startIndex = 0;
    int endIndex = array.length-1;

    while( endIndex >= startIndex )
    {
      if( endIndex == startIndex )
        return ( comparator.compare( value, array[startIndex] )==0 );
      
      int middleIndex = startIndex + ( endIndex-startIndex)/2;
      int ret = comparator.compare( value, array[ middleIndex ] );
      if( ret == 0 )
        return true;
      if( ret > 0 )
      {
        startIndex = middleIndex+1;
      }
      else
      {
        endIndex = middleIndex-1;
      }
    }
    return false;
  }
}
